import java.util.Arrays;
import java.util.Scanner;

public class Work01 {
    public static void main(String[] args) {
        // 01背包问题
        Scanner scanner = new Scanner(System.in);
        int N  = scanner.nextInt(); // 代表商品的数量
        int V  = scanner.nextInt(); // 代表背包的体积
        int[] volume = new int[N + 1];
        int[] value = new int[N + 1];
        int[][] dp = new int[N+1][V + 1];// dp[i][j]代表容量为j的背包装前i个物品最多能装的价值为多少
        for (int i = 1; i <= N; i++) {
            volume[i] = scanner.nextInt();
            value[i] = scanner.nextInt();
        }
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < V + 1; j++) {
                if(i == 0){// 只装0个物品的时候，对dp进行初始化
                    dp[i][j] = 0;
                    continue;
                }
                // 判断容量为j的时候，能不能装下第i个物品
                if(j >= volume[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-volume[i]] + value[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(Arrays.toString(value));
        System.out.println(Arrays.toString(volume));
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println(dp[N][V]);
    }
}
